package com.demo.study.algorithm.cases;

import static com.demo.study.utils.ArrayUtil.printArray;

/**
 * 有序数组合并
 *
 * @author Baymax
 * @since 2024-08-15
 */
public class C03_ArrayMerge {
    public static void main(String[] args) {
        testMerge1();
        testMerge2();
    }

    private static void testMerge1() {
        int[] array = new int[]{1, 5, 6, 2, 4, 10, 11};
        int[] target = new int[array.length];
        merge1(array, 0, 2, 3, 6, target, 0);
        printArray(target);
    }

    private static void testMerge2() {
        int[] array = new int[]{1, 5, 6, 2, 4, 10, 11};
        int[] target = new int[array.length];
        merge2(array, 0, 2, 3, 6, target);
        printArray(target);
    }

    /**
     * 方法1-递归方式
     *
     * @param array 原始数组
     * @param i 有序区间1的起始索引
     * @param iEnd 有序区间1的结束索引
     * @param j 有序区间2的起始索引
     * @param jEnd 有序区间2的结束索引
     * @param target 合并之后的有序数组
     * @param k 合并后的有序数组索引值
     */
    public static void merge1(int[] array, int i, int iEnd, int j, int jEnd, int[] target, int k) {
        if (i > iEnd) {
            // 区间1 记录完成，区间2剩余元素直接复制到after中
            System.arraycopy(array, j, target, k, jEnd - j + 1);
            return;
        }
        if (j > jEnd) {
            System.arraycopy(array, i, target, k, iEnd - i + 1);
            return;
        }
        if (array[i] < array[j]) {
            // 区间1 小于 区间2，则记录区间1的值，区间1和k索引右移
            target[k] = array[i];
            merge1(array, i + 1, iEnd, j, jEnd, target, k + 1);
        } else {
            target[k] = array[j];
            merge1(array, i, iEnd, j + 1, jEnd, target, k + 1);
        }
    }

    /**
     * 方法2-循环实现
     *
     * @param array 原始数组
     * @param i 有序区间1的起始索引
     * @param iEnd 有序区间1的结束索引
     * @param j 有序区间2的起始索引
     * @param jEnd 有序区间2的结束索引
     * @param target 合并之后的有序数组
     */
    public static void merge2(int[] array, int i, int iEnd, int j, int jEnd, int[] target) {
        int k = 0;
        while (i <= iEnd && j < jEnd) {
            if (array[i] < array[j]) {
                target[k] = array[i];
                i++;
            } else {
                target[k] = array[j];
                j++;
            }
            k++;
        }
        if (i > iEnd) {
            System.arraycopy(array, j, target, k, jEnd - j + 1);
        }
        if (j > jEnd) {
            System.arraycopy(array, i, target, k, iEnd - i + 1);
        }
    }
}